package com.gorkr.dp.pack;

/**
 * @author gorkr
 * @date 2022/06/18 16:23
 **/
public class M416PartitionEqualSubset {

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num :
                nums) {
            sum += num;
        }
        int half = sum /2;

        // dp[i][j] 对于前i个整数，不超过j时能否刚好装入 中间可有空缺
        boolean[][] dp = new boolean[nums.length + 1][half + 1];

        // base case
//        dp[1][nums[0]] = true;
        for (int i = 0; i <= nums.length; i++) {
            dp[i][0] = true;
        }


        for (int i = 1; i <=nums.length; i++) {
            for (int j = 1; j <=half; j++) {
                if(nums[i-1]>j){
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }



        return dp[nums.length][half];
    }

}
    